Self crossing¶
Time: O(N); Space: O(1); hard
You are given an array x of n positive numbers.
You: * start at point (0,0) and * moves x[0] metres to the North, then * x[1] metres to the West, * x[2] metres to the South, * x[3] metres to the East and so on.
In other words, after each move your direction changes counter-clockwise.
Write a one-pass algorithm with O(1) extra space to determine, if your path crosses itself, or not.
Example 1:
Self crossing
+---+
| |
+---+----->
|
Input: x = [2, 1, 1, 2],
Output: True
Example 2:
Not self crossing
+------+
| |
|
|
+------------->
Input: x = [1, 2, 3, 4]
Output: Fallse
Example 3:
Self crossing
+------+
| |
+------+---->
Input: x = [1, 1, 1, 1]
Output: True
[1]:
class Solution1(object):
def isSelfCrossing(self, x) -> bool:
"""
:type x: List[int]
:rtype: bool
"""
if len(x) >= 5 and \
x[3] == x[1] and \
x[4] + x[0] >= x[2]:
# Crossing in a loop
return True
for i in range(3, len(x)):
if x[i] >= x[i - 2] and \
x[i - 3] >= x[i - 1]:
# Case 2: current line crosses the line 4 steps ahead of it
# Fourth line crosses first line and onward
return True
elif i >= 5 and x[i - 4] <= x[i - 2] and \
x[i] + x[i - 4] >= x[i - 2] and \
x[i - 1] <= x[i - 3] and \
x[i - 5] + x[i - 1] >= x[i - 3]:
# Case 3: current line crosses the line 6 steps ahead of it
# Sixth line crosses first line and onward
return True
return False
[2]:
s = Solution1()
x = [2, 1, 1, 2]
assert s.isSelfCrossing(x) == True
x = [1, 2, 3, 4]
assert s.isSelfCrossing(x) == False
x = [1, 1, 1, 1]
assert s.isSelfCrossing(x) == True